МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Розрахункова робота
з дисципліни
«Проблемно-орієнтовані обчислювальні
комплекси та системи»
на тему
«Реалізація алгоритмів пошуку на графічному процесорі»
ЗМІСТ
І. Бінарний пошук 3
1.1. Бінарний пошук у CPU 3
1.2. Бінарний пошук у GPU 4
ІІ. Реалізація алгоритму SSSP на GPU 11
ІІІ. Реалізація алгоритму BFS на GPU 18
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 23
І. Бінарний пошук
Бінарний пошук у CPU
Класична реалізація бінарного пошуку у CPU досить проста в програмуванні. Інші модифікації і поліпшення можуть виявитися корисними лише за певних умов. Буде розглянуто загальний випадок. По-друге: максимум за величину порядку ln2 N порівнянь буде знайдено шуканий ключ (або установлено, що його немає в таблиці). Не багато інших алгоритмів зможуть потягатися з такою швидкодією. І так маємо в самому гіршому випадку ln2 N порівнянь. Правда алгоритм застосуємо лише для відсортованого списку. Реалізація на CPU має наступний вигляд:
__host__ void searchCPU ( float * data, int * result )
{
int x = 16777200; // шуканий елемент
int i = 0; // ліва границя масиву
int j = 16 * 1024 * 1024; // права границя масиву
int k = 0;
while ( i <= j )
{
k = i + (j - i) / 2 ;
if ( data[k] < x )
{ i = k + 1; }
else
if ( data[k] > x )
{ j = k - 1; }
else
{
result[0] = data [k];
result[1] = k;
break;
}
}
}
Як можна побачити, дійсно нічого складного. Даний алгоритм значно перевершує по швидкодії простий лінійний пошук (у багато сотень разів), реалізований навіть на GPU, адже для лінійного пошуку маємо N порівнянь в гіршому випадку. Але, як вже говорилося вище, він можливий лише для відсортованого списку (про сортування трохи нижче). До речі кажучи, цей алгоритм набагато стійкіший, оскільки для нього практично не має значення в якій частині списку перебуває елемент, тоді як для лінійного – від цього безпосередньо залежить час пошуку. Але це в реалізації на CPU! На GPU для лінійного пошуку маємо протилежний випадок тобто досить стійкий алгоритм, тому безліч потоків може майже одночасно охопити різні ділянки списку.
Бінарний пошук у GPU
Графік порівняння продуктивності для CPU і GPU, зображений на рисунку 1.
/
Рисунок 1. Графік порівняння продуктивності для CPU і GPU
Як бачимо з графіка, швидкодія GPU починає перевершувати свій аналог на CPU лише на певній позначці, тобто при досить великих обсягах динних. Спробуємо реалізувати бінарний пошук для GPU і підтвердити або спростувати дані у вищевказаному графіку. Але яким чином розділити обчислення між потоками? Перша думка була найпростіша. Розділити весь список на рівні ділянки, в кожній ділянці виконувати бінарний пошук. Потрібно зауважити, що чим менше потоків, тим швидше виконується програма, тобто її швидкодія найбільша при одному потоці.
Алгоритм такий: ділимо весь список на кількість потоків, Кожен потік дивиться один елемент і порівнює його з шуканим. Якщо це шуканий елемент чудово. Якщо поточний елемент менший, запам'ятовуємо його як нижню межу. Якщо більший запам'ятовуємо як верхню межу. Кожен з потоків знайде свій елемент більший або менший шуканого, а нам потрібні тільки граничні елементи, між якими лежить шуканий, отже, потрібно серед менших елементів залишити максимум, а серед більших мінімум. Далі повторюємо процедуру, але вже не для всього списку а для нових його меж. Повторюємо доти поки або не знайдемо елемент, або кількість елементів між нижньою і верхньою межею стане меншою кількості потоків. У такому випадку для решти елементів застосовуємо будь-який інший алгоритм, наприклад однопотоковий бінарний пошук. Розглянемо приклад.
Нехай маємо 2 048 елементів і 32 потоки. Для зручності індекси елементів у масиві і їх значення будемо вважати однаковими. Шукаємо, скажімо, елемент під номером 65 рівний 65. І так перший крок. Для кожного потоку дивимося кожен 32 елемент. тобто перший...
